#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *给你一个字符串 s，找到 s 中最长的回文子串。

 

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成
通过次数1,021,787提交次数2,790,910

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */


/*
 *
 * ## 双指针

动态规划的空间复杂度是偏高的，我们再看一下双指针法。

首先确定回文串，就是找中心然后想两边扩散看是不是对称的就可以了。

**在遍历中心点的时候，要注意中心点有两种情况**。

一个元素可以作为中心点，两个元素也可以作为中心点。

那么有人同学问了，三个元素还可以做中心点呢。其实三个元素就可以由一个元素左右添加元素得到，四个元素则可以由两个元素左右添加元素得到。

所以我们在计算的时候，要注意一个元素为中心点和两个元素为中心点的情况。

**这两种情况可以放在一起计算，但分别计算思路更清晰，我倾向于分别计算**，代码如下：

class Solution {
public:
    int left = 0;
    int right = 0;
    int maxLength = 0;
    string longestPalindrome(string s) {
        int result = 0;
        for (int i = 0; i < s.size(); i++) {
            extend(s, i, i, s.size()); // 以i为中心
            extend(s, i, i + 1, s.size()); // 以i和i+1为中心
        }
        return s.substr(left, maxLength);
    }
    void extend(const string& s, int i, int j, int n) {
        while (i >= 0 && j < n && s[i] == s[j]) {
            if (j - i + 1 > maxLength) {
                left = i;
                right = j;
                maxLength = j - i + 1;
            }
            i--;
            j++;
        }
    }
};
 *
 * */
/* 找一个中心从中心往两边扩散 判断回文*/

bool ishuiwen(const string &s, int left, int right) {
    while (left <= right) {
        if (s[left++] != s[right--])
            return false;
    }
    return true;
}

void extends(const string &s, int left, int right, int &maxLen, int &outleft, int &outright) {
    int indexSize = s.size() - 1;

    //这里不需要写个函数判断回文了 因为每次都在比较 一个一个后移比较 只需要对比left 和right就行
    while (left >= 0 && left <= right && right <= indexSize && s[left] == s[right]) {
        if ((right - left + 1) > maxLen) {
            maxLen = (right - left + 1);
            outleft = left;
            outright = right;
        }
        left--;
        right++;
    }

}

string longestPalindrome(string s) {

    // 一个数作为中间对称轴 来回扩展  例如 b   aba  babad
    // 两个数个数作为中间对称轴 来回扩展 就是两个字符串中间作为对称轴    例如   ab  baba
    int outleft = 0;
    int outright = 0;
    int maxlen = 0;

    for (int i = 0; i < s.size(); ++i) {
        extends(s, i, i, maxlen, outleft, outright);//字符串作为中间对称轴
        extends(s, i, i + 1, maxlen, outleft, outright);//两个字符串中间作为对称轴
    }

    cout << outleft << "-" << outright << s.substr(outleft, maxlen);


    return s.substr(outleft, maxlen);;
}